import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().largestRectangleArea(new int[]{2,1,5,6,2,3}));
        System.out.println(new Solution().largestRectangleArea(new int[]{2,4}));
    }
}


//单调栈
class Solution {
    //优化：仅需一遍遍历就能确定左右小于当前柱子的位置
    public int largestRectangleArea1(int[] heights) {
        int[] ltL = new int[heights.length];
        int[] ltR = new int[heights.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                int top = stack.pop();
                ltR[top] = i;
            }
            ltL[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            ltR[top] = heights.length;
        }

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (ltR[i] - ltL[i] - 1));
        }
        return maxArea;
    }

    //向右、向左两遍遍历分别确定左右小于当前柱子的位置
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;

        int[] ltL = new int[heights.length];
        Deque<Integer> stackL = new ArrayDeque<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stackL.isEmpty() && heights[i] <= heights[stackL.peek()]) {
                stackL.pop();
            }
            ltL[i] = stackL.isEmpty() ? -1 : stackL.peek();
            stackL.push(i);
        }

        int[] ltR = new int[heights.length];
        Deque<Integer> stackR = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stackR.isEmpty() && heights[i] <= heights[stackR.peek()]) {
                stackR.pop();
            }
            ltR[i] = stackR.isEmpty() ? n : stackR.peek();
            stackR.push(i);
        }

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (ltR[i] - ltL[i] - 1));
        }
        return maxArea;
    }
}


//分治，超时
class Solution1 {
    public int largestRectangleArea(int[] heights) {
        return largestRectangleArea(heights, 0, heights.length - 1);
    }

    private int largestRectangleArea(int[] heights, int l, int r) {
        if (l > r) {
            return 0;
        }

        int minIdx = l;
        for (int i = l + 1; i <= r; i++) {
            if (heights[i] < heights[minIdx]) {
                minIdx = i;
            }
        }

        return Math.max(
                heights[minIdx] * (r - l + 1),
                Math.max(largestRectangleArea(heights, l, minIdx - 1),
                        largestRectangleArea(heights, minIdx + 1, r))
        );
    }
}